#include <iostream>
#include <string>
#include <vector>
#define LL long long
using namespace std;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T;
  for (cin >> T; T; T--) {
    int n;
    string s;

    cin >> n >> s;

    LL ans = 1e18;
    for (char ch : {'a', 'b'}) {
      vector<int> pos;
      int cnt = 0;

      for (int i = 0; i < n; i++) {
        if (s[i] == ch) {
          pos.emplace_back(i - cnt++);
        }
      }
      LL tmp = 0;
      if (pos.size()) {
        int x = pos[pos.size() >> 1];
        for (int p : pos) {
          tmp += abs(x - p);
        }
      }
      ans = min(ans, tmp);
    }
    cout << ans << "\n";
  }
  return 0;
}